/**********************************************************************//**
            Meteor Firmware Platform
*-
@file   selection.c
@author Lucas
@date   2021/04/28 13:19:42
@brief  selection sort
**************************************************************************/
#include "selection.h"
#include "config.h"


// 总体的思想是，每次寻找剩余元素的最值，放置到对应位置
// 比如：n个数字的数组，
// 第一次循环，找出n个元素中的最值的索引（最坏情况遍历n次）并记录，和第0处的元素交换（swap）
// 第二次循环，从剩余的（n-1）个元素中选取最值，记录索引，和第1处的元素交换（swap）
// 后续以此类推
//
//

// 和冒泡排序的对比
// 记录索引，每次大循环仅需要一次swap操作，而非每次都进行swap操作（bubble的劣势？），
int selection_sort(int arr[],int len,int is_ascsending)
{
    int i = 0;
    int j = 0;

    // loop (n-1)
    for(i = 0;i < (len - 1);i++)
    {
        int extrame = i;
  
	// loop (n-i-1)
  	for(j = (i + 1); j < len;j++)
        {
		// 对于有重复元素的数组，可一程度提高效率
            if(arr[i] == arr[j])
                continue;

            int tmp = arr[i];
            if(is_ascsending ? (arr[extrame] < arr[j]) : (arr[extrame] > arr[j]) )
               extrame = j;
        }

        // swap
        int tmp = arr[i];
        arr[i] = arr[extrame];
        arr[extrame] = tmp;
    }

     #if RESULT_PRINT
        // print
        printf("%s\r\n",is_ascsending ? "ascending" : "descending");
        for(i = 0;i< len;i++)
        {
            printf("%d,",arr[i]);
        }
        printf("\r\n");
    #endif
    
    // seems no need to reurn a value !
    return 0;
}

